import functools

# O(n^3)
# class Solution(object):
#     def maxSumAfterPartitioning(self, arr, k):
#         @functools.cache
#         def search(i, j):
#             if j - i < k:
#                 if j == i:
#                     return arr[i]
#                 else:
#                     max_v = -float('inf')
#                     for t in range(i, j):
#                         max_v = max(search(i, t) // (t - i + 1), search(t + 1, j) // (j - t))
#                     return max_v * (j - i + 1)
#             else:
#                 max_v = -float('inf')
#                 for t in range(i, j):
#                     max_v = max(max_v, search(i, t) + search(t + 1, j))
#                 return max_v
#
#         return search(0, len(arr) - 1)

# O(n^2)
class Solution(object):
    def maxSumAfterPartitioning(self, arr, k):
        @functools.cache
        def search(i, j):
            if j - i < k:
                if j == i:
                    return arr[i]
                else:
                    max_v = max(arr[j], search(i, j - 1) // (j - i))
                    return max_v * (j - i + 1)
            else:
                max_v = -float('inf')
                for t in range(i, min(j, i + k)):
                    max_v = max(max_v, search(i, t) + search(t + 1, j))
                return max_v

        return search(0, len(arr) - 1)